#include "hashmap.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#if 1
#define DBG(fmt,...) printf(fmt,##__VA_ARGS__)
#else
#define DBG(fmt,...) 
#endif

#define string char *

#define getmem(type)			\
	(type *)malloc(sizeof(type))


/*初始哈希表数组元素个数，可设置为预估存储数据个数的2倍*/
#define DEFAULT_LIST_SIZE 8
/*是否自动扩容，可在关闭时适当调整DEFAULT_LIST_SIZE大小*/
#define IF_AUTO_ASSIGN True

/*创建哈希表，初始化*/
sHASHMAP * 
hashMap_create(void) 
{
	sHASHMAP *hashMap= getmem(sHASHMAP);

    if (hashMap == NULL) {
        return NULL;
    }

    // 起始分配8个内存空间，溢出时会自动扩充
    hashMap->list = (sENTRY *)calloc(DEFAULT_LIST_SIZE , sizeof(sHASHMAP));
    if (hashMap->list == NULL) {
		free(hashMap);
        return NULL;
    }
	
    hashMap->size = 0;
    hashMap->listSize = DEFAULT_LIST_SIZE;
	hashMap->clash_num = 0;
    hashMap->autoAssign = IF_AUTO_ASSIGN;

    return hashMap;
}


//散列函数有不同实现 1
static int ELFHash(const void* key)
{
    char * k = (char *)key;
    unsigned long h = 0;
    while (*k) {
        h = (h << 4) + *k++;
        unsigned long g = h & 0xF0000000L;
        if (g) {
            h ^= g >> 24;
        }
        h &= ~g;
    }
	
    return h;
}


/* the classic Times33 hash function 2 */
static int hash_33(const void* _key)
{
	char *key = (char*)_key;
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + hash + *key++;
    }
    return hash;
}


/*************************************************************
*函数:	hash
*参数:	键值
*返回值:hash值
*描述:	获取key的哈希值
*************************************************************/
static int hash(const void* _key)
{
	unsigned int uiSeed = 131; // 31 131 1313 13131 131313 etc..
	unsigned int uiHash = 0;
	char * key = (char *)_key;
	while (*key)
	{
		uiHash = uiHash * uiSeed + (*key++);
	}
	
	return uiHash;
}



/*统一哈希函数接口，想使用函数指针的自行设*/
static int key2index(sHASHMAP * hashMap, const void* key)
{
	if(NULL == hashMap || NULL == key) return -1;
	int a=2;
	int index = -1;
	int length = hashMap->listSize;

	/*计算哈希值*/
	switch (a)
	{
		case 0:
			index = ELFHash(key); 
			break;
		
		case 1:
			index =  hash_33(key);
			break;
		
		case 2:
		default:
			index =  hash(key);
			break;
			
	}


	/*哈希值 转成下标*/
	/*取余保证下标在数组存储空间内，也因忽略高位差异带来冲突
		使用位运算(&)来实现取模运算(%)，X % 2^n = X & (2^n - 1)二进制特点，也避免了负数出现
		所以要求hashMap->listSize为2的幂
	*/
	//index %= length;
	index &= (length-1);
	
	if(index<0){
		DBG("error hash return [%d]-->", index);
		index = -index;
		DBG("[%d]\n", index);
		
	}

	return index;
}

/*默认判断两个键的值是否相等*/
static Boolean if_value_equal(const void * key1, const void * key2)
{	if(NULL == key1 || NULL == key2) return False;
    return strcmp((string)key1, (string)key2) ? False : True;
}


/*根据new_listSize指向的空间大小，重新映射分配数据*/
void hashMap_resize(sHASHMAP * hashMap, int new_listSize) 
{
	if(NULL == hashMap) return;

	
    if (new_listSize < DEFAULT_LIST_SIZE) {
		return;
    }
	
	DBG("[resize start] size:%d listSize:%d -->%d \n", hashMap->size, hashMap->listSize, new_listSize);
    /*1.键值对临时存储空间 */ 
    sENTRY * tempList = (sENTRY *)malloc(hashMap->size * sizeof(sENTRY));
	
	if(NULL == tempList){
		DBG("error hashMap_resize, tempList\n");
		DBG("[resize finish] size listSize %d  %d \n", hashMap->size, hashMap->listSize);
		return;
	}


	/*2.原来同index的链节点在新的哈希表内可能存放在不同index，因此要暂存所有的键值对数据*/ 
    for (int i = 0, j=0; i < hashMap->listSize; i++) {
        sENTRY * entry = &hashMap->list[i];

        while (entry){
			if(entry->key){
				tempList[j].key = entry->key;
				tempList[j].value = entry->value;
				tempList[j].next = NULL;
				
				DBG("key: \"%s\" %*s value: \"%s\"\n",(char*)tempList[j].key, (int)(15-strlen((string)(tempList[j].key))), "", (string)(tempList[j].value));
				j++;

			}
			entry = entry->next;
        }
		
    }

	/*此处需要删除原数据，释放空间吗？
	添加的数据是堆中内存地址，上面暂存的也是暂存地址。数据没有复制、重复，也不需要删除
	本函数只是改变节点地址的存储位置，并未做搬运和复制键值对数据的操作
	*/
	
    /* 3.更改存储空间*/
    sENTRY * relist = (sENTRY *)realloc(hashMap->list, new_listSize * sizeof(sENTRY));
    if (NULL == relist) {
		
		/*realloc() 内存扩展动作失败返回 NULL，原来的内存并没有被释放*/
		DBG("error: 获取更多空间失败,listSize没有变化\n");
	
    }else{
		/*
		realloc()成功获得空间时，返回非零。
		此时不论返回值是多少，程序都不需要对原来的内存地址值作特殊操作。这里直接覆盖
		首先，如果申请得到的堆起始地址和原堆地址相同的情况，那说明只是在原来的内存基础上往后扩展就好，这是最简单的情况
		可是如果 不同呢？这很容易让人误解为，需要调用一次 free(原地址)。
		这是错误的，因为这个动作，realloc 会自动帮你做了，不要画蛇添足！
		所以要先释放原空间内指针指向的空间（更要先保存数据），而直接释放原空间
		
		*/
		hashMap->list = relist;
		relist = NULL;
		
		DBG("已获取新大小空间\n将数据写入新哈希表\n");
		// 初始化存储空间
	    memset(hashMap->list, 0x00, new_listSize * sizeof(sENTRY));
		
		/*暂存键值对数据数量*/
		int length = hashMap->size;

		hashMap->listSize = new_listSize;
		hashMap->size = 0;
		hashMap->clash_num=0;
	    // 将所有键值对写入新哈希表
	    for (int i = 0; i < length; i++) {
			//DBG("in key value %s %s\n", (char*)tempList[i].key, (char*)tempList[i].value);
	        hashMap_insert(hashMap, tempList[i].key, tempList[i].value);
	    }
	}

	DBG("[resize finish] now size listSize %d  %d \n", hashMap->size, hashMap->listSize);
    free(tempList);
	
}


/*
堆内创建字符串的副本
可使用c标准库函数strdup、strndup、strndupa、strdupa替代

strdup、strndup使用malloc()函数获取空间
strndupa、strdupa使用alloca()函数获取空间

区别在于，alloca分配的是调用者的栈空间，当函数结束返回时这段空间会自动释放。
而malloc分配的堆空间，不会自动释放，需要调用free()函数手动释放。

使用[本函数、strdup、strndup]，注意删除节点时释放空间
*/
static void * value_dup(const void *pValue)
{
	if(NULL == pValue) return NULL;
	
    int len;
    void * pValueDup;
	
	
    if (pValue == NULL){
		return NULL;
	}
	
	len = strlen((string)pValue)+1;/*strlen不包括结束符'\0'，所以加1*/

	/*自定的限制，可删除*/
	if(len>50){
		DBG("warn: strlen is too long \n");
		return NULL;
	}

	pValueDup = calloc(1, len );
	if(NULL == pValueDup){
		return NULL;
	}

	memcpy(pValueDup, pValue, len);

	return pValueDup;
}




/*
新加和修改一个键值对
如果key在哈希表中已经存在，就修改value，否则就是新加一个节点。
关于key和value参数有两种编写方式：
1. 调用者给出数据的堆空间地址
2. 调用者给出数据的栈空间地址，由本函数在堆空间拷贝一份
这里采用第2种
*/
void hashMap_insert(sHASHMAP * hashMap, const void * key, const void * value)
{
	if(NULL == hashMap || NULL == key || NULL == value) return;
	
    // 获取哈希值——key映射后的数组下标
    int index = key2index(hashMap, key);
	
    if (hashMap->list[index].key == NULL) {
        //该下标数组未存数据，就直接存储key,value
        hashMap->list[index].key = value_dup(key);
        hashMap->list[index].value = value_dup(value);
		hashMap->list[index].next = NULL;/*再次显式置0*/
        
		hashMap->size++;
		
    } else {
		//该下标数组已有数据（冲突出现），就先遍历，看是否有相同的key，有就修改数据，退出函数
        sENTRY * current = &hashMap->list[index];
        while (current != NULL) {
            if (if_value_equal(key, current->key)) {
                // 找到相同key，修改数据
                free(current->value);
				current->value = NULL;
                current->value = value_dup(value);
                return;
            }
            current = current->next;
        };
		
		// 遍历完，没有相同的key，意味着要在相同的数组下标下新加入数据，即解决冲突，注意删除时释放空间
        // 创建链节点插入到index对应键值对 的next ，这样数组里的键值对无需读取。
		sENTRY *entry=getmem(sENTRY);
		/*赋值*/
		entry->key = value_dup(key);
        entry->value = value_dup(value);
		/*插入，这里插入在数组节点的next，也可也考虑添加到链节点的末尾(需要遍历，效率低，若有尾节点指针，还需空间存储)*/
        entry->next = hashMap->list[index].next;
        hashMap->list[index].next = entry;

        hashMap->size++;
		hashMap->clash_num++;
    }
	DBG("[insert] key: \"%s\" %*s index %d  (%d/%d)\n",(char*)key, (int)(15-strlen((char*)key)), "", index, hashMap->size, hashMap->listSize);

    if (hashMap->autoAssign && hashMap->size >= hashMap->listSize) {

        // 内存扩充至原来的两倍
        // *注: 扩充时考虑的是当前存储元素数量与存储空间的大小关系，而不是存储空间是否已经存满，
        // 例如: 存储空间为10，存入了10个键值对，但是全部冲突了，所以存储空间空着9个，其余的全部挂在一个上面，
        // 这样检索的时候和遍历查询没有什么区别了。可以简单这样理解，当我存入第11个键值对的时候一定会发生冲突，
        // 这是由哈希函数本身的特性(取模)决定的，冲突就会导致检索变慢，所以这时候扩充存储空间，对原有键值对进行
        // 再次散列，会把冲突的数据再次分散开，加快索引定位速度。
        hashMap_resize(hashMap, hashMap->listSize * 2);
    }
}


/*
buff_len必须 > value的长度，value的长度可由hashMap_exists()获取
注意：无论是否找到，一定执行memset(ret_buff, 0x00, buff_len);
以避免在未找到情况下，误以为ret_buff数据为value的值
也可以判断返回值来确定是否找到
未找到，返回-1
找到，返回看作字符串时value的长度
*/
int hashMap_get_value(sHASHMAP * hashMap, const void * key, void * ret_buff, int buff_len)
{
	if(NULL == ret_buff) return -1;
	memset(ret_buff, 0x00, buff_len);
	
	if(NULL == hashMap || NULL == key) return -1;

	int value_len=0;

		
	// 查找时，找到index平均用时O(1)，value只能存储在同index的链表中
    // 但遍历同index链表，时间复杂度为O(n)，理想n为1。
    // 为使n为1的情况出现更多就要求，散列更平均的散列函数和更大的数组存储空间（使忽略的高位减少，保留更多的原数据信息）
    int index = key2index(hashMap, key);
	/*O(1)找到index*/
    sENTRY * entry = &hashMap->list[index];

	/*O(n)找到index*/
    while (entry != NULL) {

        if (if_value_equal(entry->key, key)) {

			value_len=strlen((string)entry->value)+1;
			if(buff_len>=value_len){
				
				memcpy(ret_buff, entry->value, value_len);
			}

            return value_len;
        }
        entry = entry->next;
    }
    
    return -1;
}

int hashMap_find(sHASHMAP * hashMap, const void * key, void * ret_buff, int buff_len)
{
	hashMap_get_value(hashMap, key, ret_buff, buff_len);
}
int hashMap_search(sHASHMAP * hashMap, const void * key, void * ret_buff, int buff_len)
{
	hashMap_get_value(hashMap, key, ret_buff, buff_len);
}


/*用户释放value中的指针指向的空间，一般key是char*不会包含指针*/
int hashMap_remove_user(sENTRY *entry)
{
	DBG("用户释放value中的指针指向的空间\n");
	
	return 0;
}



/*
这里有很三种情况需要考虑
1.哈希表为空
2.相应数据不存在，已删除
3.删除成功

在理解<删除>为真正执行了删除动作的情况下（即下面实现），1、2返回False，3返回True
如果理解<删除>为 使哈希表中该键值对不存在，本函数无需返回，一定满足理解要求
*/
int hashMap_remove(sHASHMAP * hashMap, const void * key)
{
	if(NULL == hashMap || NULL == key) return False;

    int index = key2index(hashMap, key);
    sENTRY * entry = &hashMap->list[index];
    if (entry->key == NULL) {
        return False;
    }

	/*表示是否确实删除了节点*/
    Boolean result = False;
	
    if (if_value_equal(entry->key, key)) {
		/* 数组节点 是 删除键值对*/
        hashMap->size--;
		
		hashMap_remove_user(entry);
		free(entry->key);
		free(entry->value);
		
        if (entry->next != NULL) {
			hashMap->clash_num--;
			/*有冲突链节点，把数组节点赋值为数组节点的next*/
            entry->key = entry->next->key;
            entry->value = entry->next->value;
            entry->next = entry->next->next;
			
        }else{
			entry->key = NULL;
			entry->value = NULL;
			entry->next = NULL;
		}
		
		/*数组节点尽管是堆上，但在数据结构上是数组无需单独释放，数组空间伸缩交给hashMap_resize()*/

        result = True;
		
    } else {
        sENTRY * p = entry;
        entry = entry->next;
        while (entry != NULL) {
            if (if_value_equal(entry->key, key)) {
				/* 链节点 为删除键值对*/
                hashMap->size--;
				hashMap->clash_num--;
			
				/*先挂接，再删除*/
                p->next = entry->next;

				hashMap_remove_user(entry);
				free(entry->key);
				free(entry->value);
				entry->key = NULL;
				entry->value = NULL;
				entry->next = NULL;
				
				/*链节点需要释放空间*/
				free(entry);
				entry = NULL;
				
                result = True;
                break;
            }
            p = entry;
            entry = entry->next;
        };

    }

	DBG("[remove] key: \"%s\" %*s index %d  (%d/%d)\n",(char*)key, (int)(15-strlen((char*)key)), "", index, hashMap->size, hashMap->listSize);
    // 如果空间占用不足一半，则释放多余内存
    if (result && hashMap->autoAssign &&  hashMap->size < hashMap->listSize / 2) {
		
        hashMap_resize(hashMap, hashMap->listSize / 2);
		
    }

	/*返回删除结果 */
    return result;
}

/*
判断key是否存在
存在返回value长度，value长度>=0，看作字符串包括'\0'
不存在返回-1

*/
int hashMap_exists(sHASHMAP * hashMap, const void * key)
{
	if(NULL == hashMap || NULL == key) return -1;
	int value_len=0;
    int index = key2index(hashMap, key);
    sENTRY * entry = &hashMap->list[index];
    if (entry->key == NULL) {
        return -1;
    }
    else {
        while (entry != NULL) {
            if (if_value_equal(entry->key, key)) {
				value_len=strlen((string)entry->value)+1;/*包括'\0'*/
                return value_len;
            }
            entry = entry->next;
        }
        return -1;
    }
}


/*清空哈希表，初始化为最初的8元素数组*/
void hashMap_clean(sHASHMAP * hashMap) 
{
	if(NULL == hashMap) return;
	
	sENTRY * temp;

    for (int i = 0; i < hashMap->listSize; i++) {
        /*先释放链节点空间*/
        sENTRY * entry = hashMap->list[i].next;
        while (entry != NULL) {
			hashMap->size--;
			hashMap->clash_num--;
            temp= entry;
			entry = entry->next;
		
			hashMap_remove_user(temp);
			free(temp->key);
			free(temp->value);
			temp->key = NULL;
			temp->value = NULL;
			temp->next = NULL;
			
            free(temp);
			temp = NULL;
			
        }
		
		/*再释放数组节点*/
		entry = &hashMap->list[i];

		if(entry->key){
			hashMap->size--;
			hashMap_remove_user(entry);
			free(entry->key);
			free(entry->value);
			entry->key = NULL;
			entry->value = NULL;
			entry->next = NULL;
		}
		
    }
	
	
    //重置为8个内存空间
	if(hashMap->listSize>DEFAULT_LIST_SIZE){
    	hashMap_resize(hashMap, DEFAULT_LIST_SIZE);
	}

}



void hashMap_reset(sHASHMAP * hashMap) 
{
	if(NULL == hashMap) return;

	hashMap_clean(hashMap);
}



void hashMap_delete(sHASHMAP ** hashMap) 
{
	if(NULL == hashMap) return;

	hashMap_clean(*hashMap);
	
	free((*hashMap)->list);/*释放8个空间*/
	(*hashMap)->list = NULL;
	free(* hashMap);/*释放管理结构体空间*/
	*hashMap = NULL;
}



/*迭代器参考*/

sHASHMAP_ITERATOR* hashMap_Iterator_create(sHASHMAP * hashMap) {
	if(NULL == hashMap) return NULL;

    sHASHMAP_ITERATOR* iterator = getmem(sHASHMAP_ITERATOR);
    if (iterator == NULL) {
        return NULL;
    }
    iterator->hashMap = hashMap;
    iterator->count = 0;
    iterator->index = -1;/*这里指向数组0号元素*/
    iterator->entry = NULL;
    return iterator;
}

Boolean hashMap_Iterator_hasNext(sHASHMAP_ITERATOR* iterator) {
    return iterator->count < iterator->hashMap->size ? True : False;
}

sHASHMAP_ITERATOR* hashMap_Iterator_next(sHASHMAP_ITERATOR* iterator) {
	if(NULL == iterator ) return NULL;
	
    if (hashMap_Iterator_hasNext(iterator)) {
		
        if (iterator->entry != NULL && iterator->entry->next != NULL) {
			/*有链节点，先找链节点*/
            iterator->count++;
            iterator->entry = iterator->entry->next;
        }else{
	        while (++iterator->index < iterator->hashMap->listSize) {
				/*数组节点*/
	            sENTRY * entry = &iterator->hashMap->list[iterator->index];

	            if ((NULL != entry) && (entry->key != NULL)) {
		
	                iterator->count++;
	                iterator->entry = entry;
	                break;
	            }
	        }
        }
    }
    return iterator;
}

void hashMap_Iterator_free(sHASHMAP_ITERATOR** iterator) {
	if(NULL == iterator ) return;
	
	if(*iterator){
	    free(*iterator);
	    *iterator = NULL;
	}
}